看雪.腾讯TSRC 2017 CTF 秋季赛 第五题点评及解析思路
看雪CTF快讯:
第五题已有13人破解!
导语
这道题的比赛过程可谓是精彩纷呈,十分有看点了。
群里的讨论十分火爆~大家都对这道题表达了自己的见解~
精彩的第五题结束,第五题出题者birchfire以13人的成绩,一举登上防守方第一位。
第五题过后,很多黑马让大家眼前一亮。
前十名的排名再次发生了较大的变动。poyoten升至第一名。
cqccqc冲进第四名,raycp、qwertyaa、acdxvfsvd,也是黑马,紧随其后,冲进了前十位。
第五题过去后,比赛的最终结果又开始变得扑朔迷离。
老将能否捍卫自己的宝座,而新将又是否能够一举夺魁,给我们带来新的惊喜呢?
接下来让我们一起来看看第五题的点评、出题思路和解析。
看雪评委netwind点评
本题构思精细、耐人寻味,是一道非常有趣的题目。首先作者通过int 2d 指令触发异常来进行反调试,然后采用魔方转动变换的方式对原始数据进行加密。而魔方旋转变换可以用矩阵乘法实现,通过乘以一个 48*48 的单位矩阵实现魔方的旋转变换,破解者需要分析加密过程,然后逆序操作进行解密。
brichfire,看雪论坛资深粉丝,喜欢程序逆向分析,长期从事基于污点传播方法的二进制代码分析和漏洞挖掘方法研究,特别感谢看雪论坛提供这么好的学习平台,喜欢的书有《0Day漏洞》、《Android软件安全与逆向分析》、《软件安全分析与应用》等。
1、 本题采用魔方转动变换的方式对原始数据进行加密,破解者需要分析加密过程,然后逆序操作进行解密。
魔方初始状态图,中心 a,b,c,d,e,f 是 6 个面的中心,
10 | 11 | 12 | ||||||
17 | b | 13 | ||||||
16 | 15 | 14 | ||||||
40 | 41 | 42 | 0 | 1 | 2 | 20 | 21 | 22 |
47 | e | 43 | 7 | a | 3 | 27 | c | 23 |
46 | 45 | 44 | 6 | 5 | 4 | 26 | 25 | 24 |
30 | 31 | 32 | ||||||
37 | d | 33 | ||||||
36 | 35 | 34 | ||||||
50 | 51 | 52 | ||||||
57 | f | 53 | ||||||
56 | 55 | 54 |
顺时针旋转 a 面 90°得到如下图:红色的数字是发生了置换的位置。
10 | 11 | 12 | ||||||
17 | b | 13 | ||||||
44 | 43 | 42 | ||||||
40 | 41 | 30 | 6 | 7 | 0 | 16 | 21 | 22 |
47 | e | 31 | 5 | a | 1 | 15 | c | 23 |
46 | 45 | 32 | 4 | 3 | 2 | 14 | 25 | 24 |
30 | 31 | 32 | ||||||
37 | d | 33 | ||||||
36 | 35 | 34 | ||||||
50 | 51 | 52 | ||||||
57 | f | 53 | ||||||
56 | 55 | 54 |
顺时针旋转 b 面 90°得到如下图:
16 | 17 | 10 | ||||||
15 | b | 11 | ||||||
14 | 13 | 12 | ||||||
0 | 1 | 2 | 20 | 21 | 22 | 54 | 55 | 56 |
47 | e | 43 | 7 | a | 3 | 15 | c | 23 |
46 | 45 | 44 | 6 | 5 | 4 | 14 | 25 | 24 |
30 | 31 | 32 | ||||||
37 | d | 33 | ||||||
36 | 35 | 34 | ||||||
50 | 51 | 52 | ||||||
57 | f | 53 | ||||||
42 | 41 | 40 |
顺时针旋转 c 面 90°得到如下图:
10 | 11 | 2 | ||||||
17 | b | 3 | ||||||
16 | 15 | 4 | ||||||
40 | 41 | 42 | 0 | 1 | 32 | 26 | 27 | 20 |
47 | e | 43 | 7 | a | 33 | 25 | c | 21 |
46 | 45 | 44 | 6 | 5 | 34 | 24 | 23 | 22 |
30 | 31 | 52 | ||||||
37 | d | 53 | ||||||
36 | 35 | 54 | ||||||
50 | 51 | 12 | ||||||
57 | f | 13 | ||||||
56 | 55 | 14 |
顺时针旋转 d 面 90°得到如下图:
10 | 11 | 12 | ||||||
17 | b | 13 | ||||||
16 | 15 | 14 | ||||||
40 | 41 | 42 | 0 | 1 | 2 | 20 | 21 | 22 |
47 | e | 43 | 7 | a | 33 | 27 | c | 23 |
52 | 51 | 50 | 46 | 45 | 44 | 6 | 5 | 4 |
36 | 31 | 30 | ||||||
35 | d | 31 | ||||||
34 | 35 | 32 | ||||||
24 | 25 | 26 | ||||||
57 | f | 53 | ||||||
56 | 55 | 54 |
顺时针旋转 e 面 90°得到如下图:
50 | 11 | 12 | ||||||
57 | b | 13 | ||||||
56 | 15 | 14 | ||||||
46 | 47 | 40 | 10 | 1 | 2 | 20 | 21 | 22 |
45 | e | 41 | 17 | a | 3 | 27 | c | 23 |
44 | 43 | 42 | 16 | 5 | 4 | 26 | 25 | 24 |
0 | 31 | 32 | ||||||
7 | d | 33 | ||||||
6 | 35 | 34 | ||||||
30 | 51 | 52 | ||||||
37 | f | 53 | ||||||
36 | 55 | 54 |
顺时针旋转 f 面 90°得到如下图:
22 | 23 | 24 | ||||||
17 | b | 13 | ||||||
16 | 15 | 14 | ||||||
12 | 41 | 42 | 0 | 1 | 2 | 20 | 21 | 34 |
11 | e | 43 | 7 | a | 3 | 27 | c | 35 |
10 | 45 | 44 | 6 | 5 | 4 | 26 | 25 | 36 |
30 | 31 | 32 | ||||||
37 | d | 33 | ||||||
40 | 47 | 46 | ||||||
56 | 51 | 50 | ||||||
55 | f | 51 | ||||||
54 | 53 | 52 |
无论怎么旋转,魔方中心不会改变位置,每个面有 8 个值,上图中数为 8 进
制, 6 个面共 48 个数,可以构成一个 48*1 的矩阵。而魔方旋转变换可以用矩阵乘法实现,通过乘以一个 48*48 的单位矩阵实现魔方的旋转变换。 6 个面用 6 个矩阵分别表示:如果 a 面旋转 180°就乘以 2 次 MATRIX_a, 270°就乘以 3 次。 因此,每个面的操作有 3 种, 6 个面共计 18 种。为了将输入映射到操作,可以考虑 18 进制,而输入范围包括数字和大小写字母,可以考虑用 62 进制,两个结合到一块就是 62 进制到 18 进制的转换。
int MATRIX_a[48][48];
int MATRIX_b[48][48];
int MATRIX_c[48][48];
int MATRIX_d[48][48];
int MATRIX_e[48][48];
int MATRIX_f[48][48];
3、 加密密钥:KanXueCrackMe2017,题目将其视为 62 进制数(左边是低位,右边是高位),因为合法输入包含 26*2 个大小写字母和 10 个数字共计 62 个字符,加密前先转换成 18 进制数,EDAHE450C741GH441E11BH84(左边是低位,右边是高位), 每一位作为转动魔方的一个操作码 V,用 V/3 表示要操作的面(魔方 6 个面,编号 0~5),用 V%3 表示要转动的角度, 0, 1, 2 分别表 示 顺 时 针 转 动 90 ° , 180 ° , 270 ° , 初 始 化 时 依 次 按 照EDAHE450C741GH441E11BH84 对应的动作转动魔方,得到一个混乱状态的魔方。
4、 验证过程是用户输入验证码,数字和大小写字母组合成一个 62 进制的数,
然后转换成 18 进制的数据,从低位到高位作为魔方转动的操作对魔方进行
变换,结束后检验魔方是否还原回来。
5、 从原理上,我们首先得到各个操作码的逆操作码,即操作完 V 之后操作~V
能够回到原始状态。如下表所示:这些操作码三个一组,分管一个面的操作:
V | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
~V | 2 | 1 | 0 | 5 | 4 | 3 | 8 | 7 | 6 |
V | 9 | A | B | C | D | E | F | G | H |
~V | B | A | 9 | E | F | C | H | G | F |
6、 得到解密还原的操作码序列如下:46F911C144FG147E234CFADC,另外我们知道如果连续的 2 个操作码是操作同一个面,那这 2 个操作码其实可以进行运算消除合并, 46F911C144FG147E234CFADC 中的 11 操作是第零个面连续转了 2 个 180°,可以消除舍去, 44 操作也是第一个面连续转了 2 个 180°,消除舍去, FG 操作是第五个面转了 180°后再转 270°,等价于转了 90°,化简为 H, 34 操作化简为 5 操作, DC 操作化简为 E 操作,化简合并之后得到最短的还原操作步骤如下:46F9C1H147E25CFAE,将这个值当成 18 进制(左低位右高位)转换成 62 进制(左低位右高位)得到口令:CcLaoE37J45Y
7、 魔方还原的操作步法不唯一,本题通过后面的最后一步的校验保证其唯一性,解出此题的一个关键是发现化简环节。工作流程图如下所示:
本题的反调试使用了一个小技巧, int 2d 指令触发一个异常信号,在调试和
跟踪环境下则不会触发该异常,会走到一个迭代 1000 次 base64 编码的编码过 程,然后将输入与字符串“ Vm0wd2QyUXlVWGw==”比较,这个是永远不会成立的,因为正确的编码结果是“ Vm0wd2QyUXlVWGw=”,对应的输入是
“ ImBeDebuged” ,而比较的字符串多了一个 ” =“号。 此处容易诱导解题者进
入解题误区。
1、 定位到 0x406FC3 位置的校验函数;
2、 分析 0x40700B 位置调用魔方初始化函数和 0x407030 位置调用的魔方打
乱函数,该函数位于 0x4084A3 位置,根据操作步骤调用 0x4080DF 处的函
数,根据参数旋转指定的面和转动角度。
参数 KanXueCrackMe2017,打乱步骤 EDAHE450C741GH441E11BH84
3、 分析 0x40718B 位置调用的魔方还原函数,与打乱函数相同,参数是用户
的输入,对应还原步骤。按照打乱步骤的逆序和逆操作码,得到一个还原
序列46F911C144FG147E234CFADC,得到对应的输入ieunV2phk6yPywNtJ,测试得到如下结果:
给出了提示,不是失败,而是接近成功,说明思路是对的。
另外从下面的代码看出输入字符串长度为 0xC,即 12 个字符,小于上述
逆推出来的 17 个字符。
4、 最后一 个坑。
序列 46F911C144FG147E234CFADC 是可以化简的,
46F911C144FG147E234CFADC 中的 11 操作是第 0 面连续转了 2 个 180°,可以消除舍去, 44 操作也是第 1 面连续转了 2 个 180°,消除舍去, FG 操作是第 5 面转了 180°后再转 270°,等价于转了 90°,化简为 H, 34 操作化简为 5 操作, DC 操作化简为 E 操作,化简合并之后得到更短的还原操作步骤如下:46F9C1H147E25CFAE,将这个值当成 18 进制(左低位右高位)转换成 62 进制(左低位右高位)得到口令:CcLaoE37J45Y, 刚好 12个字符, 验证成功。
相关工具:IDA、OD、python
由程序图标得知这是一个MFC程序。打开程序,随便输入sn,弹出失败对话框。
用OD打开CM,bp MessageBoxW,运行,输入sn,点击确定,触发MessageBoxW断点。栈回溯确定调用源0x407245,随即找到按钮处理函数0x4071fd。
主函数逻辑很简单,判断sub_406fc3的返回值。0弹出“失败”,1弹出“成功”,2弹出“你就差一点啦”
跟进0x406fc3函数,在正常流程中发现int 2d指令
int 2d反调试原理很简单,正常运行时int 2d触发异常,进入程序的异常处理函数。而当调试运行时,OD会处理该异常,将eip+1继续运行。
下图是CM设置的异常处理函数
patch掉int 2d,修改为jmp 0x40717d即可正常调试。
异常处理函数中有3个关键判断
判断1:(失败返回0,成功则进入判断2)
判断2:(失败返回2,成功则进入判断3)
判断3:(失败返回2,成功则返回1,整个CM校验成功)
判断1是CM最重要的部分,下面我会详细分析判断1。
作者设置判断2是为了防止程序多解。事实上,如果在分析理清了作者的算法思路,那么逆推得出的sn会自然的pass掉判断2。
判断3的逻辑一目了然,eax指向sn字符串,判断条件:strlen(sn)=0xc。同判断2,这也是一个防止多解的判断。按作者思路逆推的sn也会pass掉判断3。
下面是判断 1 的详细分析:
判断 1 的成功条件:
为了便于描述,设var_d9f4开始,大小为0x30的字节流为BLOCK1。var_d934开始,大小为0x30的字节流为BLOCK2。
成功条件就是:BLOCK1和BLOCK2全等。
在0x40718b处下断,调试发现BLOCK1和BLOCK2都被初始化过。BLOCK1被初始化为0x00-0x2F依次递增排列,BLOCK2被初始化为0x00-0x2F的乱序排列。
往前翻代码,发现如下代码:
调试发现,sub_4084A3就是初始化BLOCK1和BLOCK2的函数。初始化时,sub_4084A3被调用(传入了字符串参数”KanXueCrackMe2017“,传入了BLOCK1的地址)(事实上,BLOCK1和BLOCK2在内存中是紧挨着的,实际上做变换的是BLOCK2),判断1前,sub_4084A3再次被调用(传入了我们的sn字符串,传入了BLOCK1的地址)。
为了使判断1成功,要让BLOCK2和BLOCK1全等。调试发现,sub_4084A3并不会打乱BLOCK1,只会打乱BLOCK2。(BLOCK1一直为0x00-0x2F的递增排列)
所以我们要找的sn可以说是字符串”KanXueCrackMe2017“在函数sub_4084A3作用下的”逆“。 ”KanXueCrackMe2017“ 负责打乱递增排列的BLOCK2,而我们的SN则负责还原BLOCK2。
在打乱BLOCK之前,SN会经历4步变换。
SN的第一次变换:
进入sub_4084A3
进入sub_40829c
对sn中的每一个char做判断:
在'0'~'9' 之间则减去'0'。结果范围[0,9]
在'A'~'Z'之间则减去'7'。结果范围[10,35]
在'a'~'z'之间则减去'='。结果范围[36,61]
变换1:由字符向[0,61]区间做1对1映射。
SN的第二次变换:
同样是在sub_40829c中
第一个call sub_403641作用是初始化变量。
第二个call sub_4038E1读取向[0,61]区间映射过的sn,按位权重乘以相应个数的62。
最后两个call将这些按62位权重的数求和。
变换2:转换为62进制数字
SN的第三次变换:
变换3:62进制转换为18进制
SN的第四次变换:
变换4:[0,17]向[0-9,'A'-'H']做1对1映射
验证代码:
为了确认这4次SN的变换,通过调试,得到输入字符串” ”KanXueCrackMe2017 “,得到输出字符串"EDAHE450C741GH441E11BH84"
验证代码如下(python实现):
输出如下:
验证通过
在之前的代码中,我们的SN被变换为SN1。下面我们来看SN1是如何引导BLOCK的变换的。
SN1变换后作为sub_4080DF的参数:
SN1又被转换为了[0,17]的数字序列,每个数字除以3的商和余数作为参数传递给sub_4080DF
进入sub_4080DF(函数较长,仅截取一部分):
这种函数中就调用了一个函数sub_40727D,余数决定了调用的次数,商决定了传给该函数的01块的地址。
余数的范围[0,2],调用次数为余数+1,即[1,3]。[0,17]除以3的范围是[0,5],相对应,也有6个不同的01块。
进入sub_4072:
调试发现sub_40727d就是BLOCK变换的执行者。下文简称基函数。上图基函数有两个变量,传递进来的都是BLOCK2的地址。
但事实上,最关键的一个参数IDA并没有识别出来,就是图中的v2,通过ecx传递进来的。这个v2是一个大小为0x2400的由0和1的DWORD值组成的块。
观察上图代码,基函数通过局部变量v10保存数据,退出时,用v10覆盖BLOCK2。v10中的每个值都是由01块v2和原BLOCK2对应求积再求和而来,这0x30个积中,01块有且仅有一个为1。每次算出一个值之后,会对01块进行的错位。通过这种方式来保证每个BLOCK2中的值都能通过01块映射到v10中。就这样,基变换完成了对BLOCK2的一次置换。
01块的初始化:
01块的初始化在sub_407307中:
上图只是一个01块的初始化(一共有6个01块)
6个01块,对应着6种基函数。把置换表提取出来:
提取出置换表之后,观察置换表特点
1、有一行置换后不变
2、有一行发生了偏移为2的移位。
3,、其余4行都只有3个位置产生了置换,剩余5个位置不变。
然后就。。。。
3X3魔方6个面对应6个置换表。旋转一个面时,对立面不变,旋转面偏移2移位,其余4面变换3位。
去除中心节点,魔方共有6X(9-1)=48=0x30个小方块。完美契合CM中的置换函数。
还是用python:
结果:
SN:CcLaoE37J45Y
— END —
温馨提示
每道题结束过后都会看到很多盆友的精彩解题分析过程,因为公众号内容的限制,每次题目过后我们将选出一篇与大家分享。解题方式多种多样,各位参赛选手的脑洞也种类繁多,想要看到更多解题分析的小伙伴们可以前往看雪论坛【CrackMe】版块查看哦!
热门推荐| 看雪CTF